//在一个由 m 个用户组成的社交网络里，我们获取到一些用户之间的好友关系。两个用户之间可以相互沟通的条件是他们都掌握同一门语言。 
//
// 给你一个整数 n ，数组 languages 和数组 friendships ，它们的含义如下： 
//
// 
// 总共有 n 种语言，编号从 1 到 n 。 
// languages[i] 是第 i 位用户掌握的语言集合。 
// friendships[i] = [ui, vi] 表示 ui 和 vi 为好友关系。 
// 
//
// 你可以选择 一门 语言并教会一些用户，使得所有好友之间都可以相互沟通。请返回你 最少 需要教会多少名用户。 请注意，好友关系没有传递性，也就是说如果 
//x 和 
//y 是好友，且 
//y 和 
//z 是好友， 
//x 和 
//z 不一定是好友。
//
// 
//
// 示例 1： 
//
// 
//输入：n = 2, languages = [[1],[2],[1,2]], friendships = [[1,2],[1,3],[2,3]]
//输出：1
//解释：你可以选择教用户 1 第二门语言，也可以选择教用户 2 第一门语言。
// 
//
// 示例 2： 
//
// 
//输入：n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],
//[2,3]]
//输出：2
//解释：教用户 1 和用户 3 第三门语言，需要教 2 名用户。
// 
//
// 
//
// 提示： 
//
// 
// 2 <= n <= 500 
// languages.length == m 
// 1 <= m <= 500 
// 1 <= languages[i].length <= n 
// 1 <= languages[i][j] <= n 
// 1 <= ui < vi <= languages.length 
// 1 <= friendships.length <= 500 
// 所有的好友关系 (ui, vi) 都是唯一的。 
// languages[i] 中包含的值互不相同。 
// 
//
// Related Topics 贪心 数组 哈希表 👍 55 👎 0


package LeetCode.editor.cn;

import java.util.HashSet;
import java.util.Set;

/**
 * @author ldltd
 * @date 2025-09-10 21:34:01
 * @description 1733.需要教语言的最少人数
 */
public class MinimumNumberOfPeopleToTeach{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 MinimumNumberOfPeopleToTeach fun=new MinimumNumberOfPeopleToTeach();
	 	 Solution solution = fun.new Solution();
		solution.minimumTeachings(2, new int[][]{{1}, {2}, {1, 2}}, new int[][]{{1, 2}, {1, 3}, {2, 3}});
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 // 所有好友之间都可以交流而非所有人都可以交流
	// 需要保证好友之间是同一种语言,直接找出会的人最多的语言
	// 但是需要排除好友可能已经可以正常沟通了
		 public int minimumTeachings1(int n, int[][] languages, int[][] friendships) {
			 int m = languages.length;
			 // 将每个用户的语言转换为集合，便于查找
			 Set<Integer>[] userLanguages = new Set[m];
			 for (int i = 0; i < m; i++) {
				 userLanguages[i] = new HashSet<>();
				 for (int lang : languages[i]) {
					 userLanguages[i].add(lang);
				 }
			 }

			 // 找出需要处理的好友对（即无法交流的好友对）
			 boolean[] needHelp = new boolean[m];
			 for (int[] friendship : friendships) {
				 int u = friendship[0] - 1;
				 int v = friendship[1] - 1;

				 // 检查这对好友是否有共同语言
				 boolean hasCommon = false;
				 for (int lang : userLanguages[u]) {
					 if (userLanguages[v].contains(lang)) {
						 hasCommon = true;
						 break;
					 }
				 }

				 if (!hasCommon) {
					 needHelp[u] = true;
					 needHelp[v] = true;
				 }
			 }

			 // 如果没有需要处理的好友对，直接返回0
			 int countNeedHelp = 0;
			 for (boolean need : needHelp) {
				 if (need) countNeedHelp++;
			 }
			 if (countNeedHelp == 0) return 0;

			 // 对于每种语言，计算需要教多少人
			 int minTeach = Integer.MAX_VALUE;
			 for (int lang = 1; lang <= n; lang++) {
				 int teachCount = 0;
				 for (int i = 0; i < m; i++) {
					 if (needHelp[i] && !userLanguages[i].contains(lang)) {
						 teachCount++;
					 }
				 }
				 minTeach = Math.min(minTeach, teachCount);
			 }

			 return minTeach;
		 }

	public int minimumTeachings(int n, int[][] languages, int[][] friendships) {
		int m = languages.length;
		boolean[][] learned = new boolean[m][n + 1]; // 记录每个人学的语言
		for (int i = 0; i < m; i++) {
			for (int x : languages[i]) {
				learned[i][x] = true;
			}
		}

		boolean[] vis = new boolean[m];
		int[] cnt = new int[n + 1];

		next:
		for (int[] f : friendships) {
			int u = f[0] - 1, v = f[1] - 1; // 下标从 0 开始
			for (int x : languages[u]) {
				if (learned[v][x]) { // 两人可以相互沟通，无需学习语言
					continue next;
				}
			}
			add(u, languages, vis, cnt);
			add(v, languages, vis, cnt);
		}

		int maxCnt = 0;
		for (int c : cnt) {
			maxCnt = Math.max(maxCnt, c);
		}
		// 直接教会其余人最多人掌握的语言
		return total - maxCnt;
	}
	//有多少个人无法沟通，记作 total。
	private int total = 0;
	//遍历这个人的语言列表，把语言 x 的出现次数加一，即 cnt[x] 加一。
	private int add(int u, int[][] languages, boolean[] vis, int[] cnt) {
		if (vis[u]) {
			return total;
		}
		vis[u] = true; // 避免重复统计
		total++;
		for (int x : languages[u]) {
			cnt[x]++;
		}
		return total;
	}


}
//leetcode submit region end(Prohibit modification and deletion)

}
